package leecode.array.子串与子序列问题;

/**
 * @author wangxi created on 2021/2/27 20:26
 * @version v1.0
 * https://leetcode-cn.com/problems/longest-common-subsequence/
 *
 * https://leetcode-cn.com/problems/longest-common-subsequence/solution/1143-zui-chang-gong-gong-zi-xu-lie-dong-zde2v/
 *
 *  最长公共子序列 返回结果为具体的字符串
 */
public class LongestCommonSubSequenceV2 {
    public static void main(String[] args) {
        LongestCommonSubSequenceV2 obj = new LongestCommonSubSequenceV2();
        String res = obj.longestCommonSubsequence("1A2C3D4B56", "B1D23A456A");

        System.out.println(res);
    }

    /**
     * 返回具体的字符串，其实和求长度写法一模一样，真神奇
     *
     * 注意：此题求结果字符串不能效仿 最长公共子串的写法(因为最长公共子串 可以按照下标连续截取字符串，子序列是有可能不连续的)
     *
     */
    public String longestCommonSubsequence(String s1, String s2) {
        // write code here
        if (s1 == null || s1.length() <= 0 || s2 == null || s2.length() <= 0) {
            return "-1";
        }
        String[][] dp = new String[s1.length() + 1][s2.length() + 1];
        for (int i = 0; i <= s1.length(); i++) {
            for (int j = 0; j <= s2.length(); j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = "";
                    continue;
                }
                char c1 = s1.charAt(i - 1);
                char c2 = s2.charAt(j - 1);
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1] + c1;
                } else {
                    dp[i][j] = dp[i - 1][j].length() > dp[i][j - 1].length() ? dp[i - 1][j] : dp[i][j - 1];
                }
            }
        }
        if (dp[s1.length()][s2.length()].equalsIgnoreCase("")) {
            return "-1";
        }
        return dp[s1.length()][s2.length()];
    }
}
